package mht.practice.ListNode;

import java.util.List;

/**
 * Created by MHT on 2017/9/15.
 */
public class getMiddleNode {

    // 查找单链表的中间结点
    /**
     * 此题可应用于上一题类似的思想。也是设置两个指针，只不过这里是，两个指针同时向前走，前面的指针每次走两步，后面的指针每次走一步，
     * 前面的指针走到最后一个结点时，后面的指针所指结点就是中间结点，即第（n/2+1）个结点。注意链表为空，链表结点个数为1和2的情况。
     * 时间复杂度O(n)
     */
    public static ListNode getMiddleNode(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode q = head;      // p---q
        ListNode p = head;

        // 前面指针每次走两步，直到指向最后一个结点，后面指针每次走一步
        while (q.next != null) {
            q = q.next;
            p = p.next;
            if (q.next != null) {
                q = q.next;
            }
        }
        return p;
    }
}
